package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/next-permutation/description/">下一个排列</a>
 * <p>整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。</p>
 * <li>例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。</li>
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。
 * 更正式地，<a color="black">如果数组的所有排列根据其<b>字典顺序</b>从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。</a>
 * 如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 * <li>例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。</li>
 * <li>类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。</li>
 * <li>而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。</li>
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * 必须<a color="blue">原地</a>修改，只允许使用额外常数空间。
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,3]
 *      输出：[1,3,2]
 *
 * 示例 2：
 *      输入：nums = [3,2,1]
 *      输出：[1,2,3]
 *
 * 示例 3：
 *      输入：nums = [1,1,5]
 *      输出：[1,5,1]
 * </pre>
 * <b>提示：</b>
 * <li>1 <= nums.length <= 100</li>
 * <li>0 <= nums[i] <= 100</li>
 *
 * @author c2b
 * @since 2023/4/19 10:08
 */
public class Hot031NextPermutation_M {

    /**
     * 以 12385764 的下一个排列为例
     * 1.从后往前找到第一个相邻升序的元素对 (i,j)==》第一个右边值大于左边值的。这里 i=4，j=5，对应的值为 5，7：
     * 2.然后在 [j,end) 从后向前查找第一个大于 A[i] 的值 A[k]。这里 A[i] 是 5，故 A[k] 是 6：
     * 3.将 A[i] 与 A[k] 交换。这里交换 5、6：
     * 4.这时 [j,end) 必然是降序，逆置 [j,end)，使其升序。这里逆置 [7,5,4]：
     */
    public void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        final int end = nums.length - 1;
        for (int j = end; j > 0; --j) {
            final int i = j - 1;
            // 1.从后往前，查找一个相邻的升序的元素对(i,j。i在j的左侧)（如果存在，说明存在更大的排列，否则不存在更大的排列）
            if (nums[j] > nums[i]) {
                // 2.此时，i位置后面的元素都是按照降序排列的。从后往前，找到第一个大于nums[i]的元素(最小的大于nums[i]的元素)
                for (int k = end; k > i; --k) {
                    // 3. 因为j的存在，所以一定会找到。找到后，交换位置
                    if (nums[k] > nums[i]) {
                        int temp = nums[k];
                        nums[k] = nums[i];
                        nums[i] = temp;
                        // 此时i位置后面的所有元素仍为降序排列的，将后面元素逆序=》按照升序排列
                        reserve(nums, j, end);
                        return;
                    }
                }
            }
        }
        // 不存在更大的排序，说明数组是按照升序排列的，将数组逆序
        reserve(nums, 0, end);
    }

    public void reserve(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            ++start;
            --end;
        }
    }

    public static void main(String[] args) {
        new Hot031NextPermutation_M().nextPermutation(new int[]{1, 2, 3, 8, 5, 7, 6, 4});
    }

}
